|
|
1.
求解圆盘图中最小连通支配集的近似算法
赵学锋
计算机应用
2011, 31 (07):
1962-1965.
DOI: 10.3724/SP.J.1087.2011.01962
针对无线传感器网络常用的拓扑模型单位圆盘图，提出了基于分布式贪心策略的近似算法DDT，在算法执行的每一轮中，根据一跳邻域范围内的权值和邻居的状态信息，选举出节点并和已确定的节点连接，逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析，得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明，和相关的分布式算法相比，DDT产生的连通支配集在规模上更优。
参考文献 |
相关文章 |
多维度评价
|
|
